﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace _4Gewinnt
{
    /// <summary>
    /// Extends the class Board with the ability to redo previous moves 
    /// With the ability to redo previous moves, we only need to store one game board and just must remember the 
    /// moves which were made at the nodes of the MiniMax search tree, to be able to restore the previous state.
    /// </summary>
    public class RedoBoard
    {
        /// <summary>
        /// Stores the actual game tokens
        /// </summary>
        private GameColor[,] grid;
        /// <summary>
        /// The number of rows of the board (readonly)
        /// </summary>
        public int Rows
        {
            get { return _rows; }
        }
        private int _rows = 6;

        /// <summary>
        /// The number of columns of the board (readonly)
        /// </summary>
        public int Cols
        {
            get { return _cols; }
        }
        private int _cols = 7;

        /// <summary>
        /// The number of consecutive token needed to win
        /// </summary>
        public int ttw
        {
            get { return _ttw; }
        }
        private int _ttw;

        /// <summary>
        /// Initializes a new board
        /// </summary>
        /// <param name="ttw">The number of token needed to win (typically 4)</param>
        public RedoBoard(int ttw)
        {
            this._ttw = ttw;
            grid = new GameColor[_rows, _cols];
            for (int i = 0; i < _rows; i++)
            {
                for (int j = 0; j < _cols; j++)
                {
                    grid[i, j] = GameColor.Empty;
                }
            }
        }

        /// <summary>
        /// Initializes a new board
        /// </summary>
        /// <param name="ttw">The number of token needed to win (typically 4)</param>
        /// <param name="grid">The grid. gird gets copied during initialization</param>
        public RedoBoard(int ttw, GameColor[,] grid)
        {
            this._ttw = ttw;
            this.grid = new GameColor[_rows, _cols];
            for (int i = 0; i < _rows; i++)
            {
                for (int j = 0; j < _cols; j++)
                {
                    this.grid[i, j] = grid[i, j];
                }
            }
        }

        /// <summary>
        /// Returns an exact copy of this instance (all fields are copied)
        /// </summary>
        /// <returns>An exact copy of this instance (all fields are copied)</returns>
        public RedoBoard Clone()
        {
            return new RedoBoard(this._ttw, this.grid);
        }

        /// <summary>
        /// Finds a legal move in column <paramref name="c"/>. If there is no legal move in 
        /// <paramref name="c"/> (i.e. the column is full), -1 is returned
        /// </summary>
        /// <param name="c">The column to be searched for a legal move</param>
        /// <returns>The row number r such that (r,<paramref name="c"/>) is a legal move. 
        /// If there is no legal move in <paramref name="c"/>, -1 is returned.</returns>
        public int findLegalRowInColumn(int c)
        {
            //search rows from bottom to top for a free space
            for (int i = _rows - 1; i >= 0; i--)
            {
                if (isFieldFree(i, c))
                    return i;
            }

            //if no free space is found, return -1
            return -1;
        }


        /// <summary>
        /// Checks, whether board position (r,c) is free
        /// </summary>
        /// <param name="r">The row</param>
        /// <param name="c">The column</param>
        /// <returns>True if no token is on board position (r,c). False if out of bounds</returns>
        public bool isFieldFree(int r, int c)
        {
            //check obvious things
            if (r < 0 || r >= _rows || c < 0 || c >= _cols)
                return false;

            if (grid[r, c] == GameColor.Empty)
                return true;
            else
                return false;
        }



        /// <summary>
        /// Checks whether it is legal to move to column <paramref name="c"/>
        /// </summary>
        /// <param name="c">The column to move to</param>
        /// <returns>True, if it is legal to move to column <paramref name="c"/></returns>
        public bool isLegalColumn(int c)
        {
            if (grid[0, c] == GameColor.Empty)
                return true;
            else
                return false;
        }

        /// <summary>
        /// Move a token to (r,c). An exception is thrown if move was illegal
        /// </summary>
        /// <param name="color">The color of the token to be moved</param>
        /// <param name="c">The column</param>
        public void moveTo(GameColor color, int c)
        {
            int r = findLegalRowInColumn(c);

            //check whether move is legal
            if (r == -1)
                throw new Exception("Illegal move: You cannot move to (" + r.ToString() + "," + c.ToString() + ")");

            //apply move
            grid[r, c] = color;
        }


        /// <summary>
        /// Returns which player is at (r,c)
        /// </summary>
        /// <param name="r">The row</param>
        /// <param name="c">The column</param>
        /// <returns>The player at (r,c)</returns>
        public GameColor playerAt(int r, int c)
        {
            return grid[r, c];
        }


        /// <summary>
        /// Returns true if there are no free spaces on the board
        /// </summary>
        /// <returns>True if there are no free spaces on the board</returns>
        public bool isBoardFull()
        {
            for (int i = 0; i < _rows; i++)
            {
                for (int j = 0; j < _cols; j++)
                {
                    if (grid[i, j] == GameColor.Empty)
                        return false;
                }
            }
            return true;
        }

        /// <summary>
        /// Returns true if no token is on the field yet
        /// </summary>
        /// <returns>True if no token is on the field yet</returns>
        public bool isBoardFree()
        {
            for (int i = 0; i < _rows; i++)
            {
                for (int j = 0; j < _cols; j++)
                {
                    if (grid[i, j] != GameColor.Empty)
                        return false;
                }
            }
            return true;

        }


        /// <summary>
        /// Checks, whether <paramref name="color"/> has won
        /// </summary>
        /// <param name="color">The color</param>
        /// <returns>True if player has won</returns>
        public bool hasWon(GameColor color)
        {
            int[,] winningPosition;
            return hasWon(color, out winningPosition);
        }


        /// <summary>
        /// Checks, whether <paramref name="color"/> has won
        /// </summary>
        /// <param name="color">The color</param>
        /// <param name="winningPosition">The winning position as 4x2 Matrix</param>
        /// <returns>True if player has won</returns>
        public bool hasWon(GameColor color, out int[,] winningPosition)
        {
            //init winning Position
            winningPosition = new int[_ttw, 2];

            //the number of found continous tokens
            int nTokens;

            //search horizontal: -
            for (int r = 0; r < _rows; r++)
            {
                nTokens = 0;
                for (int c = 0; c < _cols; c++)
                {
                    //if token is found
                    if (grid[r, c] == color)
                    {
                        nTokens++;
                        winningPosition[nTokens - 1, 0] = r;
                        winningPosition[nTokens - 1, 1] = c;
                    }
                    else
                        nTokens = 0;
                    //if ttw tokens are found: the player has won, return true
                    if (nTokens == _ttw)
                        return true;
                }
            }

            //search vertical: |
            for (int c = 0; c < _cols; c++)
            {
                nTokens = 0;
                for (int r = 0; r < _rows; r++)
                {
                    //if token is found
                    if (grid[r, c] == color)
                    {
                        nTokens++;
                        winningPosition[nTokens - 1, 0] = r;
                        winningPosition[nTokens - 1, 1] = c;
                    }
                    else
                        nTokens = 0;
                    //if ttw tokens are found: the player has won, return true
                    if (nTokens == _ttw)
                        return true;
                }
            }

            //search diagonal: /
            int nDiags = _rows + _cols - 1;
            for (int d = _ttw - 1; d < nDiags - _ttw + 1; d++)
            {
                nTokens = 0;
                for (int j = 0; j <= d; j++)
                {
                    int r = j;
                    int c = d - r;

                    if (r >= 0 && r < _rows && c >= 0 && c < _cols)
                    {
                        //if token is found
                        if (grid[r, c] == color)
                        {
                            nTokens++;
                            winningPosition[nTokens - 1, 0] = r;
                            winningPosition[nTokens - 1, 1] = c;
                        }
                        else
                            nTokens = 0;
                        //if ttw tokens are found: the player has won, return true
                        if (nTokens == _ttw)
                            return true;
                    }
                }
            }


            //search diagonal: \
            for (int d = _ttw; d < nDiags - _ttw + 2; d++)
            {
                nTokens = 0;
                for (int j = 0; j <= d; j++)
                {
                    int r = j;
                    int c = _cols - (d - r);

                    if (r >= 0 && r < _rows && c >= 0 && c < _cols)
                    {
                        //if token is found
                        if (grid[r, c] == color)
                        {
                            nTokens++;
                            winningPosition[nTokens - 1, 0] = r;
                            winningPosition[nTokens - 1, 1] = c;
                        }
                        else
                            nTokens = 0;
                        //if ttw tokens are found: the player has won, return true
                        if (nTokens == _ttw)
                            return true;
                    }
                }
            }



            //return false if nothing is found
            return false;
        }

        /// <summary>
        /// Finds the uppermost token in column <paramref name="c"/>. 
        /// </summary>
        /// <param name="c">The column to be searched for a token</param>
        /// <returns>The row number r </returns>
        public int findFirstFullRow(int c)
        {
            for (int i = 0; i < _rows; i++)
            {
                if (!isFieldFree(i, c))
                {
                    return i;
                }
            }
            return _rows - 1;
        }

        /// <summary>
        /// Redos the last move done in column c
        /// </summary>
        /// <param name="c">The column where to redo the last move</param>
        public void redoMove(int c)
        {
            int r = findLegalRowInColumn(c);

            //check whether the column is not full
            if (r != -1)
            {
                grid[r + 1, c] = GameColor.Empty;
            }
            else
            {
                // Column full, we remove the top coin.
                grid[0, c] = GameColor.Empty;
            }
        }

        /// <summary>
        /// sbr: Zählt die Anzahl der 2er,3er,4er...-Reihen, die weiter vervollständigt werden können. 
        /// </summary>
        /// <param name="gameColor">Für wen gezählt werden soll</param>
        /// <returns>Array mit Anzahl der Reihen</returns>
        public int[] countNumberOfRows(GameColor gameColor)
        {
            int[] numberOfRows = { 0, 0, 0, 0, 0, 0, 0 };
            for (int i = 0; i < Cols; i++)
            {
                for (int j = 0; j < Rows; j++)
                {
                    int num = tokensInARow(i, j, gameColor);
                    numberOfRows[num]++;
                }
            }

            //3er-Reihen sind auch 3 2er-Reihen. Schmeisse diese 2er daher raus.
            for (int k = 2; k < numberOfRows.Length; k++)
            {
                numberOfRows[k] = (int)Math.Ceiling((double)numberOfRows[k] / k);
            }
            return numberOfRows;
        }

        /// <summary>
        /// sbr:
        /// Computes the number of token in a row (horizontally, vertically and diagonally) when moving own stone here. Wenn Reihe nicht weiter fortgesetzt werden kann, wird 0 zurückgegeben.
        /// </summary>
        /// <param name="c">The column</param>
        /// <param name="r">The row</param>
        /// <param param name="gameColor">Für wen wird gezählt</param>
        /// <returns>The number of tokens I have in a row if moving to column c</returns>
        private int tokensInARow(int c, int r, GameColor gameColor)
        {
            //Speichere hier, in welcher Richtung die größte Reihe war
            bool vert = false;
            bool hori = false;
            bool diag1 = false;
            bool diag2 = false;
            //Speichere hier, wo die Reihe aufgehört hat an beiden Enden. Initialisiere mit out of Spielbrett.
            int vertDownMost = 6;
            int vertUpMost = -1;
            int horiLeftMost = -1;
            int horiRightMost = 7;
            int diag1LeftMost = -1;
            int diag1RightMost = 7;
            int diag1DownMost = 6;
            int diag1UpMost = -1;
            int diag2LeftMost = -1;
            int diag2RightMost = 7;
            int diag2DownMost = 6;
            int diag2UpMost = -1;

            //if c is illegal column:
            if (r == -1)
                return -1;

            if (!isTokenOfGameColor(r, c, gameColor))
            {
                return 0;
            }

            //count stores the maximum number of consecutive tokens in this column
            int count = 0;
            int a = 0;
            int b = 0;

            //search vertical: |
            int countVert = 0;
            a = r - 1;
            b = c;
            while (isTokenOfGameColor(a, b, gameColor))
            {
                countVert++;
                a--;
                vertUpMost = a;
            }
            a = r + 1;
            b = c;
            while (isTokenOfGameColor(a, b, gameColor))
            {
                countVert++;
                a++;
                vertDownMost = a;
            }
            if (countVert > count)
            {
                count = countVert;
                vert = true;
            }
            //search horizontal: -
            int countHor = 0;
            a = r;
            b = c - 1;
            while (isTokenOfGameColor(a, b, gameColor))
            {
                countHor++;
                b--;
                horiLeftMost = b;
            }
            a = r;
            b = c + 1;
            while (isTokenOfGameColor(a, b, gameColor))
            {
                countHor++;
                b++;
                horiRightMost = b;
            }
            if (countHor > count)
            {
                count = countHor;
                hori = true;
                vert = false;
            }
            //search diagonal1: /
            int countDiag1 = 0;
            a = r + 1;
            b = c - 1;
            while (isTokenOfGameColor(a, b, gameColor))
            {
                countDiag1++;
                a++;
                b--;
                diag1LeftMost = b;
                diag1DownMost = a;
            }
            a = r - 1;
            b = c + 1;
            while (isTokenOfGameColor(a, b, gameColor))
            {
                countDiag1++;
                a--;
                b++;
                diag1RightMost = b;
                diag1UpMost = a;
            }
            if (countDiag1 > count)
            {
                count = countDiag1;
                diag1 = true;
                hori = false;
                vert = false;
            }
            //search diagonal2: \
            int countDiag2 = 0;
            a = r + 1;
            b = c + 1;
            while (isTokenOfGameColor(a, b, gameColor))
            {
                countDiag2++;
                a++;
                b++;
                diag2DownMost = a;
                diag2RightMost = b;
            }
            a = r - 1;
            b = c - 1;
            while (isTokenOfGameColor(a, b, gameColor))
            {
                countDiag2++;
                a--;
                b--;
                diag2UpMost = a;
                diag2LeftMost = b;
            }
            if (countDiag2 > count)
            {
                count = countDiag2;
                diag2 = true;
                diag1 = false;
                hori = false;
                vert = false;
            }

            //Prüfe für 3er Reihen ob diese noch weiter erweitert werden können
            if (count == 2)
            {
                //prüfe, ob die vertikale Reihe erweitert werden kann
                if (vert)
                {
                    if (isFieldEmpty(vertUpMost, c) || isFieldEmpty(vertDownMost, c))
                    {
                        return count + 1;
                    }
                }
                //prüfe, ob die horizontale Reihe erweitert werden kann
                if (hori || countHor == 2)
                {
                    if (isFieldEmpty(r, horiLeftMost) || isFieldEmpty(r, horiRightMost))
                    {
                        return count + 1;
                    }
                }
                //prüfe, ob die diagonale Reihe / erweitert werden kann
                if (diag1 || countDiag1 == 2)
                {
                    if (isFieldEmpty(diag1DownMost, diag1LeftMost) || isFieldEmpty(diag1UpMost, diag1RightMost))
                    {
                        return count + 1;
                    }
                }
                //prüfe, ob die diagonale Reihe \ erweitert werden kann
                if (diag2 || countDiag2 == 2)
                {

                    if (isFieldEmpty(diag2UpMost, diag2LeftMost) || isFieldEmpty(diag2DownMost, diag2RightMost))
                    {
                        return count + 1;
                    }
                }
                return 0;
            }

            return count + 1;
        }

        /// <summary>
        /// sbr: Liefert die Positionen von Bedrohungen zurück.
        /// </summary>
        /// <param name="gameColor">Wessen Bedrohungen sollen gezählt werden</param>
        /// <returns>Eine Liste von Listen. Die "äußere" List stellt die Zeile dar, die "innere" List die Zeilen mit den Bedrohungen.</returns>
        public List<List<int>> countThreats(GameColor gameColor)
        {
            List<List<int>> threats = new List<List<int>>(7);
            threats.Add(new List<int>(6));
            threats.Add(new List<int>(6));
            threats.Add(new List<int>(6));
            threats.Add(new List<int>(6));
            threats.Add(new List<int>(6));
            threats.Add(new List<int>(6));
            threats.Add(new List<int>(6));
            GameColor gc = gameColor;

            for (int c = 0; c < Cols; c++)
            {
                for (int r = 0; r < Rows; r++)
                {
                    if (!isFieldEmpty(r, c))
                    {
                        continue;
                    }
                    this.hasWon(gameColor);
                    int count1 = 0;
                    int count2 = 0;
                    //is there a vertical | threat somewhere
                    int a = r + 1;
                    int b = c;

                    while (isTokenOfGameColor(a, b, gameColor))
                    {
                        count1++;
                        a++;
                    }

                    a = r - 1;
                    b = c;

                    while (isTokenOfGameColor(a, b, gameColor))
                    {
                        count2++;
                        a--;
                    }

                    if (count1 + count2 >= 3)
                    {
                        threats.ElementAt(c).Add(r);
                        continue;
                    }

                    //is there a horizontal - threat
                    a = r;
                    b = c + 1;
                    count1 = 0;
                    count2 = 0;

                    while (isTokenOfGameColor(a, b, gameColor))
                    {
                        count1++;
                        b++;
                    }

                    a = r;
                    b = c - 1;

                    while (isTokenOfGameColor(a, b, gameColor))
                    {
                        count2++;
                        b--;
                    }
                    if ((count1 + count2) >= 2)
                    {
                        threats.ElementAt(c).Add(r);
                        continue;
                    }

                    //is there a diagonal 1 / threat
                    a = r - 1;
                    b = c + 1;
                    count1 = 0;
                    count2 = 0;

                    while (isTokenOfGameColor(a, b, gameColor))
                    {
                        count1++;
                        b++;
                        a--;
                    }

                    a = r + 1;
                    b = c - 1;

                    while (isTokenOfGameColor(a, b, gameColor))
                    {
                        count2++;
                        b--;
                        a++;
                    }
                    if (count1 + count2 >= 3)
                    {
                        threats.ElementAt(c).Add(r);
                        continue;
                    }

                    //is there a diagonal 2 \ threat
                    a = r - 1;
                    b = c - 1;
                    count1 = 0;
                    count2 = 0;

                    while (isTokenOfGameColor(a, b, gameColor))
                    {
                        count1++;
                        b--;
                        a--;
                    }

                    a = r + 1;
                    b = c + 1;

                    while (isTokenOfGameColor(a, b, gameColor))
                    {
                        count2++;
                        b++;
                        a++;
                    }
                    if (count1 + count2 >= 3)
                    {
                        threats.ElementAt(c).Add(r);
                        continue;
                    }
                }
            }
            return threats;
        }

        /// <summary>
        /// Checks whether the token of "gameColor" is on (r,c). 
        /// </summary>
        /// <param name="r">The row</param>
        /// <param name="c">The column</param>
        /// <param name="gameColor">Der Spieler, für den gekuckt werden soll, ob es sein Stein ist</param>
        /// <returns>True, if my token is on (r,c). False, if (r,c) is outside the grid. </returns>
        private bool isTokenOfGameColor(int r, int c, GameColor gameColor)
        {
            if (r >= 0 && r < Rows && c >= 0 && c < Cols)
            {
                if (playerAt(r, c) == gameColor)
                    return true;
            }
            return false;
        }

        /// <summary>
        /// Checks whether token on (r,c) is empty. 
        /// </summary>
        /// <param name="r">The row</param>
        /// <param name="c">The column</param>
        /// <param name="board">The board</param>
        /// <returns>True, if my token on (r,c) is empty. False, if not. </returns>
        private bool isFieldEmpty(int r, int c)
        {
            if (r >= 0 && r < Rows && c >= 0 && c < Cols)
            {
                if (isFieldFree(r, c))
                    return true;
            }
            return false;
        }

        /// <summary>
        /// sbr: Wird aufgerufen, wenn es in einer Spalte mindestens 2 direkt aufeinander folgende Bedrohungen durch "gameColor" gibt. Versucht eine Spalte zurückzuliefern, die diese Bedrohungen möglichst gut verhindert. 
        /// Sind beide Bedrohungen erzeugt durch 2 3er-Reihen, die einen gemeinsamen Stein haben, liefere die Spalte, in der dieser gemeinsame Stein liegt in der Hoffnung zurück, dass dieser nur in unserer Vorschau
        /// dort liegt. Ansonsten liefere eine Spalte direkt neben der Bedrohung zurück. 
        /// </summary>
        /// <param name="threatList">Die Liste mit Bedrohungen in der Zeile c</param>
        /// <param name="c">Die Zeile, in der mehrere aufeinanderfolgende Bedrohungen auftreten</param>
        /// <param name="gameColor">Nach wessen Bedrohung wird gesucht</param>
        /// <returns>Tupel als Position, an die der Stein gelegt werden muss, um die doppelte Bedrohung zu verhindern</returns>
        public Tuple<int, int> getDoubleThreatKiller(List<int> threatList, int c, GameColor gameColor)
        {
            List<Tuple<int, int>> firstThreats = new List<Tuple<int, int>>();

            for (int i = 0; i < threatList.Count; i++)
            {
                //sbr: Schaue dich in der direkten Umgebung aller Bedrohungen um, und kucke, woher die Bedrohnung kommen könnte.
                if (isTokenOfGameColor(threatList.ElementAt(i), c - 1, gameColor))
                {
                    firstThreats.Add(new Tuple<int, int>(c - 1, threatList.ElementAt(i)));
                }
                if (isTokenOfGameColor(threatList.ElementAt(i) + 1, c - 1, gameColor))
                {
                    firstThreats.Add((new Tuple<int, int>(c - 1, threatList.ElementAt(i) + 1)));
                }
                if (isTokenOfGameColor(threatList.ElementAt(i) + 1, c, gameColor))
                {
                    firstThreats.Add((new Tuple<int, int>(c, threatList.ElementAt(i) + 1)));
                }
                if (isTokenOfGameColor(threatList.ElementAt(i) + 1, c + 1, gameColor))
                {
                    firstThreats.Add((new Tuple<int, int>(c + 1, threatList.ElementAt(i) + 1)));
                }
                if (isTokenOfGameColor(threatList.ElementAt(i), c + 1, gameColor))
                {
                    firstThreats.Add((new Tuple<int, int>(c + 1, threatList.ElementAt(i))));
                }
            }

            //sbr: Prüfe hier, ob es eine Position eines Steins gibt, die zweimal in der Liste vorkommt. Das könnte der Stein sein, der die beiden Bedrohungen erzeugt.
            int[] counts = new int[7];
            for (int i = 0; i < firstThreats.Count; i++)
            {
                for (int j = 0; j < firstThreats.Count; j++)
                {
                    if (i != j)
                    {
                        counts[firstThreats.ElementAt(i).Item1]++;
                        if (firstThreats.ElementAt(i).Item1 == firstThreats.ElementAt(j).Item1
                            && firstThreats.ElementAt(i).Item2 == firstThreats.ElementAt(j).Item2)
                        {
                            return firstThreats.ElementAt(i);
                        }
                    }
                }
            }

            int col = counts.Max();

            for (int i = 0; i < firstThreats.Count; i++)
            {
                if (firstThreats.ElementAt(i).Item1 == col)
                {
                    return firstThreats.ElementAt(i);
                }
            }

            //sbr: Gibt es keine Position eines Steins, die zweimal vorkommt, hoffe, dass durch Legen in eine direkt benachbarte Spalte das Problem gelöst wird
            if (c <= 4)
            {
                return new Tuple<int, int>(c - 1, threatList.ElementAt(0));
            }
            else
            {
                return new Tuple<int, int>(c + 1, threatList.ElementAt(0)); ;
            }

        }
    }
}
